public class SevenSort {
    //
    //
    //直接插入排序
    public void insertionSort(int[] array) {
        int len = array.length;
        for(int i = 1;i < len; i ++) {
            int tmp = array[i];
            int j = i - 1;
            for(;j >= 0; j--) {
                if(array[j] < tmp) {
                    break;
                }
                array[j + 1] = array[j];
            }
            array[j + 1] = tmp;
        }
    }
    //
    //
    //希尔排序
    public void shellSort(int[] array) {
        int len = array.length;
        int gap = len/2;
        while(gap > 0) {
            insertionSort1(array,gap);
            gap = gap / 2;
        }
    }
    private void insertionSort1(int[] array,int gap) {
        int len = array.length;
        for(int i = 1;i < len; i ++) {
            int tmp = array[i];
            int j = i - gap;
            for(;j >= 0; j -= gap) {
                if(array[j] < tmp) {
                    break;
                }
                array[j + gap] = array[j];
            }
            array[j + gap] = tmp;
        }
    }
    //
    //
    //选择排序
    public void selectionSort(int[] array) {
        int len = array.length;
        for(int i = 0; i < len ; i ++ ) {
            int j = i + 1;
            int tmp = i;
            for(;j < len; j ++) {
                if(array[j] < array[tmp]) {
                    tmp = j;
                }
            }
            swap(array,i,tmp);
        }
    }
    private void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    //
    //
    //堆排序
    public void heapSort(int[] array) {
        creeateBigHeap(array);
        int end = array.length - 1;
        while(end > 0) {
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    private void creeateBigHeap(int[] array) {
        for(int parent = (array.length-2)/2;parent >=0;parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    //
    //
    //冒泡排序
    private void shiftDown(int[] array ,int parent,int len) {
        int child = 2*parent + 1;
        while(child < len) {
            if(child+1 < len && array[child] < array[child +1]) {
                child++;
            }
            if(array[parent] < array[child]) {
                swap(array,child,parent);
                parent = child;
                child = 2*parent + 1;
            } else {
                break;
            }
        }
    }
    public void bubbleSort(int[] array) {
        int len = array.length;
        for(int i = 0;i < len ; i ++) {
            Boolean bo = true;
            for(int j = 0; j < len - i - 1; j ++) {
                if(array[j] > array[j + 1]) {
                    swap(array,j,j+1);
                    bo = false;
                }
            }
            if(bo) {
                return;
            }
        }
    }
    //
    //
    //快排
    public void quickSort (int[] array) {
        int left = 0;
        int right = array.length - 1;
        quick(array,left,right);
    }
    private void quick(int[] arr,int start,int end) {
        if( start >= end) {
            return;
        }
        int p = center1(arr,start,end);
        quick(arr,p +1,end);
        quick(arr,start,p - 1);

    }
    private int center(int[] arr,int start,int end) {
        int conunt = arr[start];
        while(start < end) {
            while(start < end && arr[end] >= conunt) {
                end--;
            }
            arr[start] = arr[end];
            while (start < end && arr[start] <= conunt){
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = conunt;
        return start;
    }
    private int center1(int[] arr,int start,int end) {
        int prev = start;
        int fast = start + 1;
        int tmp = arr[start];
        while (fast <= end) {
            if(arr[fast] <= tmp && arr[++prev] != arr[fast]) {
                swap(arr,fast,prev);
            }
            fast++;
        }
        swap(arr,prev,start);
        return prev;
    }
    //
    //
    //归并排序
    public void mergerSort(int[] array) {
        merger(array,0,array.length-1);
    }
    private void merger(int[] array,int left,int right) {
        if(left >= right)
        {
            return;
        }
        int cmd = (left + right) / 2;
        merger(array,cmd+1,right);
        merger(array,left,cmd);
        merger1(array,left,cmd,cmd+1,right);
    }
    private void merger1(int[] arr,int l1,int r1,int l2,int r2) {
        int start = l1;
        int[] tmp = new int[r2 - l1 + 1];
        int i = 0;
        while(l1 <= r1 && l2 <= r2) {
            if(arr[l1] <= arr[l2]) {
                tmp[i++] = arr[l1++];
            }
            if(arr[l2] <= arr[l1]) {
                tmp[i++] = arr[l2++];
            }
        }
        while(l1 <= r1) {
            tmp[i++] = arr[l1++];
        }
        while (l2 <= r2) {
            tmp[i++] = arr[l2++];
        }
        for (int j = 0; j < tmp.length; j++) {
            arr[j + start] = tmp[j];
        }
    }
}
